#include <iostream>
#include <cmath>
#include <vector>
using namespace std;


constexpr int MAX_HEIGHT =  15;

class Node {
public:
    int ne[MAX_HEIGHT];
    int val;
    int height;
};

class Skiplist {
public:

    Node tr[50005];
    int cur{2};

    Skiplist() {
        tr[0].val = -1;
        tr[0].height = MAX_HEIGHT - 1;
        for (int i = 0; i < MAX_HEIGHT; ++i) tr[0].ne[i] = 1;
        tr[1].val = 2e9;
        tr[1].height = MAX_HEIGHT - 1;
    }

    bool search(int target) {
        int cur = 0;
        int cur_height = MAX_HEIGHT - 1;
        while (cur_height >= 0) {
            if (tr[tr[cur].ne[cur_height]].val > target) {
                cur_height -= 1;
            } else {
                cur = tr[cur].ne[cur_height];
            }
        }
        return tr[cur].val == target;
    }

    void add(int num) {

        auto ans = search(num);
        if (ans) return;
        int height = rand() % MAX_HEIGHT;
        int cur_idx = cur++;
        vector<int> pre(height + 1);
        int cur = 0;
        int cur_height = MAX_HEIGHT - 1;
        while (cur_height >= 0) {
            if (tr[tr[cur].ne[cur_height]].val > num) {
                if (cur_height <= height) {
                    pre[cur_height] = cur;
                }
                cur_height --;
            } else {
                cur = tr[cur].ne[cur_height];
            }
        }
        tr[cur_idx].val = num;
        tr[cur_idx].height = height;
        for (int i = 0; i <= height; ++i) {
            tr[cur_idx].ne[i] = tr[pre[i]].ne[i];
            tr[pre[i]].ne[i] = cur_idx;
        }
    }

    bool erase(int num) {
        auto ans = search(num);
        if (!ans) return false;
        vector<int> pre(MAX_HEIGHT);
        int cur = 0;
        int cur_height = MAX_HEIGHT - 1;
        while (cur_height >= 0) {
            if (tr[tr[cur].ne[cur_height]].val >= num) {
                pre[cur_height] = cur;
                cur_height --;
            } else {
                cur = tr[cur].ne[cur_height];
            }
        }
        cur = tr[cur].ne[0];
        for (int i = 0; i <= tr[cur].height; ++i) {
            tr[pre[i]].ne[i] = tr[cur].ne[i];
        }
        return true;
    }
};

int main() {

    Skiplist sk;
//     ["Skiplist","add","add","add","search","add","search","erase","erase","search"]
// [[],[1],[2],[3],[0],[4],[1],[0],[1],[1]]
    sk.add(1);
    sk.add(2);
    sk.add(3);
    cout << sk.search(0) << endl;
    sk.add(4);
    cout << sk.search(1) << endl;
    cout << sk.erase(0) << endl;
    cout << sk.erase(1) << endl;
    cout << sk.search(1) << endl;
    return 0;

}